package main.leetcode.offer.firstround.from03to50;

import main.datastruc.TreeNode;

import java.util.HashMap;

/**
 * 07.重建二叉树
 *
 * <p>输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 *
 * <p>限制： 0 <= 节点个数 <= 5000
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex07 {

    HashMap<Integer, Integer> map;

    public static void main(String[] args) {
        int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {9, 3, 15, 20, 7};
        new ex07().buildTree(preorder, inorder);
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) map.put(inorder[i], i);

        TreeNode res = buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
        return res;
    }

    /**
     * 递归建立二叉树
     *
     * @param preorder 前序遍历
     * @param startPre 前序遍历起始下标
     * @param endPre 前序遍历终止下标
     * @param inorder 中序遍历
     * @param startIn 中序遍历起始下标
     * @param endIn 中序遍历终止下标
     * @return 子树根节点
     */
    public TreeNode buildTree(
            int[] preorder, int startPre, int endPre, int[] inorder, int startIn, int endIn) {
        if (startPre > endPre && startPre > endIn) return null;
        TreeNode root = new TreeNode(preorder[startPre]);
        int index = map.get(preorder[startPre]);
        //    for (int i = startIn; i <= endIn; i++) {
        //      if (inorder[i] == preorder[startPre]) {
        //        index = i;
        //        break;
        //      }
        //    }
        root.left =
                buildTree(
                        preorder,
                        startPre + 1,
                        startPre + index - startIn,
                        inorder,
                        startIn,
                        index - 1);
        root.right =
                buildTree(
                        preorder,
                        startPre + index - startIn + 1,
                        endPre,
                        inorder,
                        index + 1,
                        endIn);
        return root;
    }
}
